'''
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

 

示例 1：


输入：head = [1,2,3,4]
输出：[2,1,4,3]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/swap-nodes-in-pairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
'''
# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution(object):
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        # 空链表或者只有一个节点，直接返回
        if not head or head.next == None:
            return head

        # 创建虚拟节点
        dummyHead = ListNode(-1)

        # 初始化pre、p 节点
        pre = dummyHead
        p = head

        # 必须是节点数是偶数个的时候才能交换
        # 如果最后只剩下一个节点，即链表是奇数个节点，最后一个不用反转
        # 比如 head = [1,2, 3, 4, 5],输出 [2, 1, 4, 3, 5]
        while p and p.next:
            # 初始化 q 节点
            q = p.next

            # 交换节点 3 步走
            pre.next = q
            p.next = q.next
            q.next = p

            # 指针右移
            pre = p
            p = p.next

        # 返回链表
        return dummyHead.next

head = [1,2,3,4]
Solution().swapPairs(head)